#include <iostream>
#include <vector>

using namespace std;

template <class K,class V>
struct HashData
{
	pair<K, V> _kv;
	HashData* _next;
	HashData(const pair<K,V>& kv)
		:_kv(kv)
		, _next(nullptr)
	{}
};

template <class K>
struct _hash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct _hash<string>
{
	size_t operator()(const string& key)
	{
		size_t hashi = 0;
		for (auto e : key)
		{
			hashi += e;
			hashi *= 131;
		}
		return hashi;
	}
};

template <class K, class V,class hash=_hash<K>>
class HashTable
{
public:
	typedef HashData<K, V> Data;
	typedef HashTable<K, V> Self;

	HashTable(size_t size = 10)
	{
		_table.resize(size,nullptr);
		_n = 0;
	}

	~HashTable()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			Data* cur = _table[i];
			while (cur)
			{
				Data* next = cur->_next;
				delete cur;
				cur = next;
			}
			_table[i] = nullptr;
		}
	}

	Data* Find(const K& key)
	{
		hash hs;
		size_t hashi = hs(key) % _table.size();
		Data* ptr = _table[hashi];
		while (ptr)
		{
			if (ptr->_kv.first == key)
				return ptr;
			ptr = ptr->_next;
		}
		return nullptr;
	}

	bool Insert(const pair<K, V>& kv)
	{
		if (Find(kv.first))
			return false;

		if (_n == _table.size())
		{
			size_t newsize = _n * 2;
			//Self newtable(newsize);
			vector<Data*> newtable(newsize,nullptr);
			hash hs;

			for (size_t i = 0; i < _table.size(); i++)
			{
				Data* cur = _table[i];
				while (cur)
				{
					Data* next = cur->_next;
					size_t hashi = hs(cur->_kv.first) % newtable.size();
					cur->_next = newtable[hashi];
					newtable[hashi] = cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
			_table.swap(newtable);
		}
		hash hs;

		size_t hashi = hs(kv.first) % _table.size();
		Data* newdata = new Data(kv);

		newdata->_next = _table[hashi];
		_table[hashi] = newdata;

		++_n;
		return true;
	}

	bool Erase(const K& key)
	{
		Data* ptr = Find(key);
		hash hs;

		if (ptr)
		{
			size_t hashi = hs(ptr->_kv.first) % _table.size();
			Data* cur = _table[hashi];

			if (cur->_next == nullptr)
			{
				_table[hashi] = nullptr;
				return true;
			}

			Data* pre = nullptr;
			while (cur)
			{
				Data* next = cur->_next;
				if (cur->_kv.first == key)
				{
					pre->_next = cur->_next;
					delete cur;
					return true;
				}

				pre = cur;
				cur = next;
			}
		}
		return false;
	}

private:
	vector<Data*> _table;
	size_t _n;
};

int main()
{
	HashTable<int,int> ht;
	ht.Insert(make_pair(23, 23));
	ht.Insert(make_pair(13, 13));
	ht.Insert(make_pair(34, 34));
	ht.Insert(make_pair(3, 3));
	ht.Insert(make_pair(1, 1));
	ht.Insert(make_pair(5, 5));
	ht.Insert(make_pair(4, 4));

	ht.Erase(23);
	ht.Insert(make_pair(3, 3));
	ht.Insert(make_pair(53, 53));

	return 0;
}